APPROACH TO PROGRAMMING OF NONDETERMINISTIC GAMES (PART I: DESCRIPTION OF GENERAL HEURISTICS)

Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), B.Melnikov@tltsu.ru
Mel'nikova Elena Anatol'evna, Candidate of physical and mathematical sciences, associate professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), E.Melnikova@tltsu.ru

004.8.023, 004.83

Background. The article considers several approaches used in programming intelligent nondeterministic games – the approaches that have not been described in authors’ previous publications. The methods of algorithmization, developed and realized by the authors, deal with the search tree, modified specially for the nondeterministic games, and represent an addition (sometimes an alternative) to the neural network methods. It is important to note that the developed algorithms may be applied not only directly in the nondeterministic games, but in other problems of discrete optimization.
Materials and methods. After realization of the algorithms of statistical evaluation of the position (carried out either by standard approaches to intelligent games programming, or by neural network methods) the final (dynamic) evaluation of the position is calculated by all deterministic values obtained for all possible realizations of a random event. These values are averaged by a special method, and the results of the said averaging are considered as a dynamic value. From the physical point of view the applied averaging gives the center of gravity position of one-dimensional system of bodies, the mass of which is set by a special function – the so-called risk function. The coordinates of bodies correspond to the de-terministic values depending, similarly to the regular method of minimax, only on the deterministic factors of the game. To determine the sequence of nondeterministic searching tree tops’ processing the authors build special heuristic functions (preference functions), on the basis of which the researchers apply sorting in each of two sets of tops. The said preference functions depend on the following parameters: depth of the current top of the game tree; previous evaluation of the position; value of the reached depth of searching. Simultaneously with the building of the evaluation function with the help of the expert the authors considered several problems relating to the algorithms of automated building of such functions. The three-layer neural network with reverse error distribution was used as the approximation of the static evaluation of the position.
Results. The results of the study are not just the developed programs for intelligent nonde-terministic games, but also the application description of the considered “game” approaches in various problems of discrete optimization.
Conclusions. Practical results of the programs, created on the basis of the considered algorithms, show the advantages of the authors’ approach to the sequence of nondeterministic searching tree tops’ processing in comparrison with the approaches similar to the exhaustive search.

algorithmics, nondeterministic games, search tree.

1. Mel'nikov B. F., Radionov A. N. Izvestiya RAN. Programmirovanie [Proceedings of the Russian Academy of Sciences. Programming]. 1998, no. 5, pp. 55–62.
2. Mel'nikov B. F. Izvestiya RAN. Programmirovanie [Proceedings of the Russian Academy of Sciences. Programming]. 2001, no. 5, pp. 63–80.
3. Mel'nikov B. F. Kibernetika i sistemnyy analiz. NAN Ukrainy [Cybernetics and system analysis. National Academy of Sciences of Ukraine]. 2006, no. 3, pp. 32–42.
4. Melnikov B. 8-th International Conference on High Performance Computing and Grid in Asia Pacific Region, IEEE Computer Society Press Ed. Beijing, China (HPC-Asia), 2005, pp. 73–80.
5. Melnikov B, Radionov A., Gumayunov V. 8 th International Conference on Enterprise Information Systems, aphos. Cyprus, ICEIS, 2006, pp. 360–364.
6. Mel'nikov B. F., Mel'nikova E. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Ser. Estestvennye nauki [University proceedings. Volga region. Series: Natural sciences]. 2007, no. 6 (33), pp. 3–11.
7. Baumgertner S. V., Mel'nikov B. F. Vestnik Voronezhskogo gosudarstvennogo universiteta. Ser. sistemnyy analiz i informatsionnye tekhnologii [Bulletin of Voronezh State University. Ser. System analysis and information technologies]. 2010, no. 1, pp. 5–7.
8. Rassel S., Norvig P. Iskusstvennyy intellekt – sovremennyy podkhod [Artificial intelligence – modern approach]. Moscow; Saint Petersburg; Kiev: Vil'yams, 2006, 1410 p.
9. Michie D. Advanced in Programming and Non-Numerical Computation,Pergamon Ed.Oxford,1966,pp.183–200.
10. Hauk T., Buro M., Schaeffer J. Rediscovering *-minimax search. Computers and Games, 2004, pp. 35–50.
11. Lyuger D. Iskusstvennyy intellekt – strategii i metody resheniya slozhnykh problem
[Artificial intelligence – strategies and methods of complex problem solution]. Moscow; Saint Petersburg; Kiev: Vil'yams, 2003, 864 p.
12. Billings D. University of Alberta (USA), Ph. D. thesis, 2006, 211 p.
13. Tesauro G. Neural Computation. 1989, vol. 1, no. 3, pp. 321–32.
14. Adel'son-Vel'skiy G. M., Arlazarov V. L., Donskoy M. V. Programmirovanie igr [Programming of games]. Moscow: Nauka, 1978, 255 p.
15. Adel'son-Vel'skiy G. M., Arlazarov V. L., Bitman A., Donskoy M. V. Mashina igraet v shakhmaty [Machine plays chess]. Moscow: Nauka, 1983, 207 p.